题目描述

原题

Description:

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

原题翻译

描述：

给定一个字符串，找到最长的不重复子串的长度。

例1：

输入：“abcabcbb”
输出：3
解释：最长的不重复子串为”abc”，长度为3。

例2：

输入：“bbbbb”
输出：1
解释：最长的不重复子串为”b”，长度为3。

例3：

输入：“pwwkew”
输出：3
解释：最长的不重复子串为”wke”，长度为3。
注意，答案必须是子字符串，“pwke”是子数组而不是子字符串。

解法一

主要思想

遍历String对应的char[]，将char和index放入Map，对Map中已有的char进行覆盖。

运行速度：超过了64.86%的解答。

内存使用：超过了99.76%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if(len <= 1)
            return len;
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        int temp = 0;
        int max = 0;
        for(int i = 0; i < len; i++) {
            if(!map.containsKey(chars[i])) {
                map.put(chars[i], i);
                temp++;
            } else {
                if(i - map.get(chars[i]) > temp) { // 当前字母不在temp里
                    temp++;
                } else {
                    max = Math.max(max, temp);
                    temp = i - map.get(chars[i]);
                }
                map.put(chars[i], i);
            }
        }
        max = Math.max(max, temp);
        return max;
    }
}

解法二

主要思想

利用StringBuilder的API。

运行速度：超过了86.34%的解答。

内存使用：超过了52.36%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        StringBuilder substring = new StringBuilder();
        int longestLength = 0;
        for(int i =0; i< s.length(); i++) {
            String currentLetter = Character.toString(s.charAt(i));
            if (substring.indexOf(currentLetter) != -1 ) { // StringBuilder中已存在该字符
                longestLength = Math.max(substring.length(), longestLength);
                int endIndexToDelete = substring.indexOf(currentLetter) +1;
                substring.delete(0, endIndexToDelete);
            }
            substring.append(currentLetter);
        }
        longestLength = Math.max(substring.length(), longestLength);
        return longestLength;
    }
}

解法三

第一名答案，难以想象它竟然是一位中国人给出的(代码里有中文注释)。作为一个中国人，给出一个String，他竟然能想到ascii码…

主要思想

一个boolean[128]表示128个ascii字符。

运行速度：超过了99.82%的解答。

内存使用：超过了89.62%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        boolean[] exist = new boolean[128]; // 表示acii码的128个字符
        int max = 0, start = 0; // start用来记录无重复子串的开始位置
        for (int i = 0, len = s.length(); i < len; i++) {
            char c = s.charAt(i);
            if (exist[c]) { 
                max = Math.max(max, i - start);
                // 每次当数组中出现一个重复字符 c 的时候，将之前一个重复的 c 之前的元素设为未出现（exist[i]=false）
                for (int j = start; j < i; j++) {
                    if (s.charAt(j) == c) {
                        start = j + 1;
                        break;
                    }
                    exist[s.charAt(j)] = false;
                }
            } else {
                exist[c] = true;
            }
        }
        return Math.max(s.length() - start, max);        
    }
}